Міністерство освіти та науки України Національний університет «Львівська політехніка» Кафедра автоматизованих систем управління
Лабораторна робота №2 з дисципліни «Теорія алгоритмів і математичні основи представлення знань» на тему: “ Елементарна криптографія” Львів - 2008 Мета: ознайомитись з методами криптографії Теоретичні відомості Криптологія є . наукою, яка поділяється на криптографію та криптоаналіз. Однак досить часто термін криптографія вживається у загальнішому розумінні як синонім до криптології. Захист інформації є ширшою галуззю, що охоплює крім теоретичних основ також технічні засоби, юридичні аспекти тощо. Тайнопис також е ширшим поняттям. Крім криптографічних, він допускає й такі способи збереження таємниці, при яких повідомлення ніяк не перетворюється, а приховується сам факт його існування чи пересилання. Прикладом може служити використання невидимого чорнила. Вживання термінів код та кодування як синонімів до шифру та шифрування є не лише архаїчним, а часто й помилковим. Код — це усталене правило для заміни одиниць інформації (букв, слів, цілих фраз) певними символами. Наприклад, S0S є кодом прохання про допомогу, а згідно із ASCII кодом літера а кодується двійковою послідовністю 1100001. Коди, які вивчає математична теорія кодування, застосовуються з метою дещо протилежною до криптографічної. Повідомлення шифрується для того, щоб воно стало незрозумілим, а кодується для того, щоб бути зрозумілим навіть після часткового спотворення із-за природних перешкод у каналі зв'язку. Ці два терміни слід чітко розмежовувати тому, що на практиці одна й та ж інформація може підлягати обом діям — у типовій ситуації текст закодовують у двійкову послідовність, її шифрують, а отриманий криптотекст перед відправленням кодують за допомогою коду, який дозволить виправити помилки після передачі. Як рівноправні терміни ми будемо вживати дієслова шифрувати і криптувати та віддієслівні іменники шифрування і криптування. Виключно справою смаку є вибір між словосполученнями розкрити криптосистему та зламати криптосистему. Нарешті, Термін криптотекст має синонім криптограма, який щоправда зустрічається частіше у популярній, ніж у фаховій літературі. Класичні методи шифрування: 2.1. Шифри простої заміни перетворюють відкритий текст таким чином, що кожен символ замінюється на якийсь інший. При цьому однаковим символам у відкритому тексті відповідають однакові символи у криптотексті, а різним — різні. Ключем є табличка, що вказує в який саме символ переходить кожен символ відкритого тексту. Для прикладу, шифр Цезаря в українському алфавіті задається таким ключем: абвгґдеєжзиіїйклмнопрстуфхцчшщьюя гґдеєжзиіїйклмнопрстуфхцчшщьюяабв При шифруванні кожна буква, яка зустрічається у повідомленні, шукається у верхньому рядку і замінюється відповідною буквою із нижнього рядка (пропуски між словами та розділові знаки ігноруються). Наприклад, криптографія перетворюється у нуйтхсеугчкв. Шифр зсуву є звуженням загального шифру заміни на сукупність лише п ключів, у яких нижній рядок є циклічним зсувом верхнього рядка. Ключ такого гатунку повністю визначається довжиною зсуву s. Можна вважати, що 0 ≤ s < п, оскільки зсуви на s і на s + п позицій дають однаковий результат. Інші підкласи шифру простої заміни розглядаються у § 11.3. 2.2. Частотний аналіз. Як нам відомо з попереднього пункту, шифр заміни над n-символьним алфавітом має n! ключів. Для значень п = 26,33 (латинський та український алфавіти) це число є дуже великим. Для його оцінки можна скористатись варіантом формули Стірлінга B.I, звідки для п = 26 отримуємо п > 10 26. Число справді велике — нагадаємо, що наша планета існує лише 109 років, а наступний льодовиковий період очікується через 14000 років, тобто 4,41504 • 1011 секунд [137]. Це співставлення переконливо засвідчує безперспективність брутальної атаки на шифр заміни, однак цього недостатньо аби стверджувати, що він є надійним. Виявляється, успішний криптоаналіз можливий за допомогою частотного методу. Частота символу у ...